package com.hqq.exercise.array;

/**
 * NumAppearance 数组中只出现一次的数字
 * 题目描述:
 * 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O（n），空间复杂度为O（1）
 * 思路:
 * 1.根据两个相同的数字异或一定是0 如果求一个数组中唯一一个没有出现2次的数字可以把所有的数字进行异或 异或的非0结果就是该数字
 * 2.该题要找出两个没有出现2次的数字 因此可以考虑把数组分成两部分 每部分含有一个目标数字 这样只要分别对每个数组进行异或就可以得出该结果
 * 3.如果分成两个子数组呢？首先对原数组进行异或 得到的结果是两个目标数组的异或结果 根据第一个非0位数字上的值为1还是0可以把数组拆成两个子数组
 * 技巧:
 * 求两个数是否相同 可以通过异或为0判断
 * Created by heqianqian on 2017/8/22.
 */
public class NumAppearance {

    public static int[] findNumAppearanceOne(int[] array) {
        if (array == null || array.length == 0) {
            return null;
        }

        int[] result = new int[2];

        /*求目标数的异或结果*/
        int xor = xorArray(array, array.length);

        //求第一个非0位
        int firstBit1 = findFirstBit1(xor);

        /*两个结果数*/
        int result1 = 0;
        int result2 = 0;

        /*根据第一个非0位分成两个子数组*/
        for (int i = 0; i < array.length; i++) {
            if (isBit1(array[i], firstBit1)) {
                result1 ^= array[i];
            } else {
                result2 ^= array[i];
            }
        }

        result[0] = result1;
        result[1] = result2;

        return result;
    }

    /**
     * 求整个数组的异或结果
     */
    private static int xorArray(int[] array, int size) {
        int result = 0;
        for (int i = 0; i < size; i++) {
            result ^= array[i];
        }
        return result;
    }

    /**
     * 找一个数的第一个非0位
     */
    private static int findFirstBit1(int number) {
        int index = 0;
        while ((number & 1) == 0) {
            number = number >> 1;
            ++index;
        }
        return index;
    }


    /**
     * 判断一个数的某一位是否为1
     */
    private static boolean isBit1(int number, int index) {
        for (int i = 0; i < index; i++) {
            number = number >> 1;
        }
        return (number & 1) == 1;
    }

}
